public class Solution147 {
    public ListNode insertionSortList(ListNode head) {
        head = new ListNode(0, head);
        ListNode t = head.next;
        ListNode p = t.next;
        while (p != null) {
            if (p.val >= t.val) {
                t = p;
            } else {
                ListNode q = head;
                while (q.next.val < p.val) {
                    q = q.next;
                }
                t.next = p.next;
                p.next = q.next;
                q.next = p;
            }
            p = t.next;
        }
        return head.next;
    }
}
